昨天我們使用了 Array 來實作佇列，今天我們要來用鏈結串列來實施佇列。

方法一：Single Linked List

我們使用單向鏈結串列（Single Linked List）來實作，在 Linked List 佇列實作中，最重要的就是要討論佇列為空以及佇列非空的情況了。

0. 前情提要：先定義 Node Structure：一個屬性存資料（Data），一個屬性存放指標（next），指向下一個節點。接著再定義兩個指標：front, rear，front 指向前端之節點，rear 指向尾端之節點
1. create(Q)：將 front, rear 都設為 null
2. 在這個例子中，我們不實作 isEmpty(Q)，將他留到 enqueue 和 dequeue 時說明，isFull(Q) 則是因為使用鏈結串列，所有本來就不需要實作。
3. enqueue(Q, item)：如果佇列（Queue）為空，代表 rear 及 front 皆指向 null，此時先 new 一個節點，將 item 放入 data 欄位，並將 next 指標設為 null，接著 rear 指標應該指向新節點，重點在於 front 需要從 null 移動到新節點上，因為只有一個節點代表其為尾端也為前端元素。
   如果 Queue 非空，則一樣 new 一個節點，將 item 放入 data 欄位，並將 next 指標設為 null，接下來需要將尾端（rear）元素的 next 指向新節點，最後才將 rear 指向新節點，front 不需移動。
   示意圖：
   
4. dequeue(Q)：假設 queue 非空（rear 及 front 未指向 null）。如果 dequeue 後佇列為空，也就是說目前只有一個節點在 Queue 中，那麼用一暫時指標 p 指向等等要回收的節點，並取出裡面的 data，接著將 front 向前移一個節點（剛好是 null，因為 queue 中只有一個節點），再來須將 rear 也指向 null，最後回收 p 及 return data。
   如果 Queue 中多於一個元素，那麼一樣用暫時指標 p 指向等等要回收的節點，並取出裡面的 data，接著將 front 向前移一個節點，再來直接回收 p 及 return data。
   示意圖：
   

方法二：Circular Linked List

環狀鏈結串列（Circular Linked List）與單向鏈結串列最大的不同就在於：串列尾端元素不會指向 null，而是指向開頭元素，因此只需要一個 rear 指標即可，不須 front 和 rear 兩個指標。

0. 前情提要：先定義 Node Structure：一個屬性存資料（Data），一個屬性存放指標（next），指向下一個節點。接著再定義一個指標： rear，rear 指向尾端之節點
1. create(Q)：將 rear 設為 null
2. 在這個例子中，我們不實作 isEmpty(Q)，將他留到 enqueue 和 dequeue 時說明，isFull(Q) 則是因為使用鏈結串列，所有本來就不需要實作。
3. enqueue(Q, item)：如果佇列（Queue）為空，代表 rear 皆指向 null，此時先 new 一個節點，將 item 放入 data 欄位，並將 next 指標設為 自己，接著 rear 指標應該指向新節點。
   如果 Queue 非空，則一樣 new 一個節點，將 item 放入 data 欄位，重點為；將 next 指標設為 目前尾端節點之 next，也就是開頭，接下來需要將尾端（rear）元素的 next 指向新節點，最後才將 rear 指向新節點。
   示意圖：
   
4. dequeue(Q)：假設 queue 非空（rear 未指向 null）。如果 dequeue 後佇列為空，也就是說目前只有一個節點在 Queue 中，那麼用一暫時指標 p 指向等等要回收的節點，並取出裡面的 data，再來須將 rear 指向 null，最後回收 p 及 return data。
   如果 Queue 中多於一個元素，那麼一樣用暫時指標 p 指向等等要回收的節點，並取出裡面的 data，接著將 尾端節點的 next 指向 p 的下個節點（此動作等於更改 front），最後回收 p 及 return data。rear 不須變動。
   示意圖：
   

C++ code

#include <iostream>
#include <limits.h>
using namespace std;

typedef struct node{
    int data;
    struct node* next;
}node_t;

class Queue{
    // Single LL
    private:
        node_t* front;
        node_t* rear;
    public:
        Queue();
        void enqueue(int item);
        int dequeue();
};

Queue::Queue(){
    front = nullptr;
    rear = nullptr;
}

void Queue::enqueue(int item){
    node_t* newNode = new node_t;
    newNode->data = item;
    newNode->next = nullptr;
    if(front == nullptr){
        front = newNode;
    }else{
        rear->next = newNode;
    }
    rear = newNode;
}

int Queue::dequeue(){
    if(front == nullptr){
        cout << "dequeue fail." << endl;
        return INT_MIN;
    }
    node_t* p = front;
    int temp = p->data;
    front = p->next;
    if(front == nullptr) rear = nullptr; // now queue is empty
    delete p;
    return temp;
}

#include <iostream>
#include <limits.h>
using namespace std;

typedef struct node{
    int data;
    struct node* next;
}node_t;

class Queue{
    // Circular LL
    private:
        node_t* rear;
    public:
        Queue();
        void enqueue(int item);
        int dequeue();
};

Queue::Queue(){
    rear = nullptr;
}

void Queue::enqueue(int item){
    node_t* newNode = new node_t;
    newNode->data = item;
    if(rear == nullptr){
        newNode->next = newNode;
    }else{
        newNode->next = rear->next;
        rear->next = newNode;
    }
    rear = newNode;
}

int Queue::dequeue(){
    if(rear == nullptr){
        cout << "dequeue fail." << endl;
        return INT_MIN;
    }
    node_t* p = rear->next;
    int temp = p->data;
    if(p->next == p) rear = nullptr; // now queue is empty
    else{
        rear->next = p->next;
    }
    delete p;
    return temp;
}